package com.wangbo.basic.single;

/**
 * 单链表工具类
 */
public class SingleLinkedListUtil {

    public static class Node{
        public int value;
        public Node next; // 指针，指向后继节点

        public Node(int data) {
            this.value = data;
        }
    }

    /**
     * 反转链表，借助 next newHead head三个指针
     */
    public static Node reverse(Node head) { // 遍历指针，从原链表头遍历到末尾
        Node next = null;  // 暂存指针，指向原链表head节点的后继节点
        Node newHead = null; // 暂存指针，新链表头指针

        while (head != null) {
            next = head.next; // next指针指向head节点后继
            head.next = newHead; // head节点后继指针指向newHead节点，表示head节点断开原链表，连接新链表
            newHead = head; // newHead指针指向head节点
            head = next; // head指针右移
        }

        return newHead;
    }

    /**
     * 删除链表中值为 value 的节点
     */
    public static Node remove(Node head, int value) {
        // 删除头部值为 value 的节点
        while (head != null && head.value == value) {
            head = head.next;
        }

        Node pre = head;
        Node cur = head;
        while (cur != null) {
            if (cur.value == value) {
                pre.next = cur.next;
            } else {
                pre = cur;
            }
            cur = cur.next;
        }

        return head;
    }
}
